/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */

var treeToDoublyList = function (root) {
    if (!root) {
        return null
    }
    let res = []
    // 中序遍历
    inorderTraversal(root)
    // right指针指向
    for (let i = 0; i < res.length - 1; i++) {
        res[i].right = res[i + 1]
    }
    res[res.length - 1].right = res[0]
    // left指针指向
    for (let i = 1; i < res.length; i++) {
        res[i].left = res[i - 1]
    }
    res[0].left = res[res.length - 1]
    return res[0]
    // 中序遍历数组 将之放入res
    function inorderTraversal(root) {
        if (!root) {
            return
        }
        inorderTraversal(root.left)
        res.push(root)
        inorderTraversal(root.right)
    }
};